package com.example.demo.leetcode;

import java.util.*;

/**
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 * <p>
 * 注意：解集不能包含重复的组合。
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 输出:
 * [
 * [1,1,6],
 * [1,2,5],
 * [1,7],
 * [2,6]
 * ]
 * 示例 2:
 * <p>
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 输出:
 * [
 * [1,2,2],
 * [5]
 * ]
 */
public class Leetcode40 {

    public static void main(String[] args) {
        int[] a = {10, 1, 2, 7, 6, 1, 5};
        List<List<Integer>> lists = new Leetcode40().combinationSum(a, 8);
        System.out.println(lists);
    }

    /**
     * 超限制了
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Set<List<Integer>> result = new HashSet<>();
        dfs(candidates, target, 0, result, new LinkedList<>());
        return new ArrayList<>(result);
    }

    //输入：candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
    // * [
    // * [1,1,6],
    // * [1,2,5],
    // * [1,7],
    // * [2,6]
    // * ]

    // 组合一般都会有一个起点 因为不需要包含重复元素
    private void dfs(int[] candidates, int target, int start, Set<List<Integer>> result, LinkedList<Integer> stack) {
        // 排序
        Arrays.sort(candidates);
        // stack里求和
        // 递归退出条件 ，先忽略
        if (0 > target) {
            return;
        }
        if (target == 0) {
            result.add(new ArrayList<>(stack));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            int candidate = candidates[i];
            // !!!!!剪枝
            if (target < candidate) {
                continue;
            }
            stack.push(candidate);
            // 1 1  2 5 6 7 10  target=8
            // 第二个1 就可以跳过了
            if (i > start && candidates[i - 1] == candidate) {
                continue;
            }
            // 下面这种就不行 上面就可以
            //            if (i < candidates.length - 1 && candidates[i + 1] == candidate) {
            //                continue;
            //            }
            dfs(candidates, target - candidate, i + 1, result, stack);
            stack.pop();
        }
    }
}
